ff1588d761d55f48f61a52249e1dcc24

<!DOCTYPE html>

<title>CART (Algorithmus)</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">CART (Algorithmus)</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">CART (Classification and Regression Trees) ist ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a>, der zur <a href="Entscheidung" title="Entscheidung">Entscheidungsfindung</a> dient. Er wird bei <a href="Entscheidungsbaum" title="Entscheidungsbaum">Entscheidungsbäumen</a> eingesetzt.

Der CART-Algorithmus wurde erstmals 1984 von <a href="Leo_Breiman" title="Leo Breiman">Leo Breiman</a> et al. publiziert.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Allgemeines">Allgemeines</h2></div>

Ein bedeutendes Merkmal des CART-Algorithmus ist, dass nur <a href="Bin%C3%A4rbaum" title="Binärbaum">Binärbäume</a> erzeugt werden können, das heißt, dass an jeder Verzweigung immer genau zwei Äste vorhanden sind. Das zentrale Element dieses Algorithmus ist also das Finden einer optimalen binären Trennung.

Beim CART-Algorithmus wird die Attributsauswahl durch die Maximierung des Informationsgehalts gesteuert. CARTs zeichnen sich dadurch aus, dass sie die Daten in Bezug auf die <a href="Klassifikation" title="Klassifikation">Klassifikation</a> optimal trennen. Dies wird mit einem Schwellwert erreicht, der zu jedem Attribut gesucht wird. Der Informationsgehalt eines Attributes wird als hoch erachtet, wenn durch die Auswertung der sich aus der Teilung über die Schwellwerte ergebenden Attributausprägungen mit einer hohen Trefferquote eine Klassifikation vorgenommen werden kann.

Bei den Entscheidungsbäumen, welche durch den CART-Algorithmus berechnet werden, gilt: Je höher der Informationsgehalt eines Attributs in Bezug auf die Zielgröße, desto weiter oben im Baum findet sich dieses Attribut.

Die Entscheidungsschwellwerte ergeben sich jeweils durch die Optimierung der <a href="Entropie_(Informationstheorie)" title="Entropie (Informationstheorie)">Spaltenentropie</a>. Die Gesamtentropien der Attribute ergeben sich durch ein gewichtetes Mittel aus den Spaltenentropien.

<div class="mw-heading mw-heading2"><h2 id="Mathematische_Beschreibung">Mathematische Beschreibung</h2></div>

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D}}=\{(x^{(i)},y_{i})\}_{i=1}^{m}}">

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}=\{(x^{(i)},y_{i})\}_{i=1}^{m}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ee5480c7faccf36638eb53bc44b047ab067aa7b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:18.306ex; height:3.509ex;" alt="{\displaystyle {\mathcal {D}}=\{(x^{(i)},y_{i})\}_{i=1}^{m}}" loading="lazy"> die Menge der Trainingsdaten mit Eingabevariablen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{(i)}=(x_{1}^{(i)},\dots ,x_{n}^{(i)})\in {\mathcal {X}}}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(i)}=(x_{1}^{(i)},\dots ,x_{n}^{(i)})\in {\mathcal {X}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/52cd2a1ce6e6a3f73b8c5d9db1489a89616ba17a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:25.028ex; height:3.676ex;" alt="{\displaystyle x^{(i)}=(x_{1}^{(i)},\dots ,x_{n}^{(i)})\in {\mathcal {X}}}" loading="lazy"> und Ausgabewerten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in {\mathcal {Y}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in {\mathcal {Y}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2fca6d018a308729c9ef591e40b7744f1c752c50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.656ex; height:2.509ex;" alt="{\displaystyle y\in {\mathcal {Y}}}" loading="lazy">. Ein Entscheidungsbaum <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> ist formal darstellbar mittels einer Funktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{T}:{\mathcal {X}}\rightarrow {\mathcal {Y}}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{T}:{\mathcal {X}}\rightarrow {\mathcal {Y}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2bb30686b35a97a2bccc60db1bbc2188ef706199.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.615ex; height:2.509ex;" alt="{\displaystyle f_{T}:{\mathcal {X}}\rightarrow {\mathcal {Y}}}" loading="lazy">, die jeder Eingabe eine Vorhersage des Ausgabewertes zuordnet. Der CART Algorithmus zur Erzeugung eines solchen Baumes findet selbständig die Verzweigungen (<a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a>) und assoziierten Regeln zur Trennung der Daten (enS split rule), mit denen diese Zuordnung möglichst optimal wird.

<div class="mw-heading mw-heading3"><h3 id="Regression">Regression</h3></div>

Sei zunächst <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {Y}}\subseteq \mathbb {R} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {Y}}\subseteq \mathbb {R} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1bd92d883ccde46c398c619b815038938fbf3d3c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.436ex; height:2.509ex;" alt="{\displaystyle {\mathcal {Y}}\subseteq \mathbb {R} }" loading="lazy">, d. h. die Ausgabe ist ein <a href="Quantit%C3%A4t" title="Quantität">quantitatives</a> Merkmal und der zu konstruierende Baum soll ein <a href="Regressionsanalyse" title="Regressionsanalyse">Regressionsproblem</a> lösen. Um einen optimalen Baum zu finden, muss erst einmal ein Trainingskriterium (<a href="Fehlerfunktion" title="Fehlerfunktion">Fehlerfunktion</a>) definiert werden. Typischerweise wird dafür die <a href="Mittlere_quadratische_Abweichung" title="Mittlere quadratische Abweichung">Mittlere quadratische Abweichung</a> genutzt:

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(T,{\mathcal {D}})={\frac {1}{m}}\sum _{i=1}^{m}(f_{T}(x^{(i)})-y_{i})^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/439848547c7a922ffe73b8ca33035ff78d3a17b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:33.153ex; height:6.843ex;" alt="{\displaystyle E(T,{\mathcal {D}})={\frac {1}{m}}\sum _{i=1}^{m}(f_{T}(x^{(i)})-y_{i})^{2}}" loading="lazy">,</dd></dl>

welche dann minimiert wird. Die Fehlerfunktion ist allerdings generell frei wählbar.

Jedem <a href="Bl%C3%A4tter_und_innere_Knoten_in_der_Graphentheorie" title="Blätter und innere Knoten in der Graphentheorie">Blatt</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> wird eine Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{l}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c9f2439c2bbf45ac826eebcd1bca00db560479be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.486ex; height:2.509ex;" alt="{\displaystyle R_{l}}" loading="lazy"> zugeordnet, sodass für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"> Blätter die zugeordneten <a href="Disjunkt" title="Disjunkt">disjunkten</a> Mengen eine <a href="Partition_(Mengenlehre)" title="Partition (Mengenlehre)">Partition</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> bilden. Man sucht nun einen Schätzwert, der für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{(i)}\in R_{l}}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(i)}\in R_{l}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/91ff6f8e8f56563a3b0b3a5c74a34a5fa0219c03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.736ex; height:3.176ex;" alt="{\displaystyle x^{(i)}\in R_{l}}" loading="lazy"> möglichst nahe an den wahren Werten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{y_{i}\;|\;x^{(i)}\in R_{l}\}}">

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{y_{i}\;|\;x^{(i)}\in R_{l}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74dc8feaaa274c3b508e8ef95d0b0f316b9f1e80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.937ex; height:3.343ex;" alt="{\displaystyle \{y_{i}\;|\;x^{(i)}\in R_{l}\}}" loading="lazy"> liegt. Der Schätzer

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{T}(x^{(i)}\in R_{l})={\textrm {mean}}(y_{i}\;|\;x^{(i)}\in R_{l})=:{\hat {c}}_{l}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7864ad21a39da0622ba594e775a4fa721daf5762.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.776ex; height:3.343ex;" alt="{\displaystyle f_{T}(x^{(i)}\in R_{l})={\textrm {mean}}(y_{i}\;|\;x^{(i)}\in R_{l})=:{\hat {c}}_{l}}" loading="lazy"></dd></dl>

liefert dafür eine Lösung. Da die Berechnung aller möglichen Bäume nicht auf effiziente Weise umsetzbar ist, eignet sich für diesen Ansatz ein <a href="Greedy-Algorithmus" title="Greedy-Algorithmus">Greedy-Algorithmus</a> am besten. D.h. konkret: Man beginnt mit einem Baum, der nur aus einem Knoten besteht und findet dann sukzessive lokal optimale Verzweigen. An jedem Knoten bestimmt man das Merkmal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy">, das alle Einträge des Elternknoten am besten in zwei Regionen unterteilen kann, wobei immer auch eine optimale Teilungsvorschrift gefunden werden muss. Für <a href="Ordinalskala" title="Ordinalskala">ordinale</a> Merkmale erfolgt dies mittels Schranke <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">, welche die beiden Regionen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{1}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}\leq s\}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{1}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}\leq s\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/16b3c906021d3e383b87047b206e6687ace1b589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:26.077ex; height:4.009ex;" alt="{\displaystyle R_{1}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}\leq s\}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{2}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}>s\}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{2}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}>s\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/94ac79819fad4a63494784f7d233fd9ffff88095.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:26.077ex; height:4.009ex;" alt="{\displaystyle R_{2}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}>s\}}" loading="lazy"> für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{(i)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{(i)}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1496c4d490e7559a75be174f3ead8fedafd6c19c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.409ex; height:2.843ex;" alt="{\displaystyle x^{(i)}}" loading="lazy"> in der ursprünglichen Partition des Elternknotens so erzeugt, dass die Fehlerfunktion minimiert wird. Sind die Merkmale nicht ordinal, ergeben sich die Verzweigungsvorschriften anhand der Zuordnung zu den verschiedenen Merkmalsausprägungen. Formal lässt sich das schreiben als

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{j,s}{\big (}\min _{c_{1}}\sum _{x^{(i)}\in R_{1}(j,s)}(y_{i}-c_{1})^{2}+\min _{c_{2}}\sum _{x^{(i)}\in R_{2}(j,s)}(y_{i}-c_{2})^{2}{\big )}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0001d1d378869be51c60d7894fad9723bd2799d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:55.481ex; height:6.509ex;" alt="{\displaystyle \min _{j,s}{\big (}\min _{c_{1}}\sum _{x^{(i)}\in R_{1}(j,s)}(y_{i}-c_{1})^{2}+\min _{c_{2}}\sum _{x^{(i)}\in R_{2}(j,s)}(y_{i}-c_{2})^{2}{\big )}}" loading="lazy">,</dd></dl>

wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {c}}_{k}={\textrm {mean}}(y_{i}\;|\;x^{(i)}\in R_{k}(j,s))_{k=1,2}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {c}}_{k}={\textrm {mean}}(y_{i}\;|\;x^{(i)}\in R_{k}(j,s))_{k=1,2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4024e443ccce3bee8f23579587ef79a68145b81b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:35.05ex; height:3.509ex;" alt="{\displaystyle {\hat {c}}_{k}={\textrm {mean}}(y_{i}\;|\;x^{(i)}\in R_{k}(j,s))_{k=1,2}}" loading="lazy"> jeweils die beiden Summen minimiert.

Ausgehend von dem einzelnen Knoten, fügt man also in jedem Schritt zwei neue Knoten hinzu, die wiederum solange weiter verzweigt werden, bis eine Abbruchbedingung (z. B. die maximale Pfadlänge von der Wurzel bis zu den Blättern) erfüllt ist.

<div class="mw-heading mw-heading4"><h4 id="Pruning">Pruning</h4></div>

Da der Baum so in den meisten Fällen zu komplex, also anfällig für <a href="%C3%9Cberanpassung" title="Überanpassung">Überanpassung</a> (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> overfitting) ist, kann (sollte) er gestutzt werden (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> <a href="Pruning" title="Pruning">Pruning</a>). Überanpassung lässt sich verhindern, indem in der Fehlerfunktion ein Regulationsterm (vgl. <a href="Englische_Sprache" title="Englische Sprache">englisch</a> Regularization) eingeführt wird, der nicht von den Daten abhängt und die Komplexität des Entscheidungsbaumes bestraft. Dadurch wird unterbunden, dass der Baum spezifische Eigenschaften der Trainingsdaten lernt, die im Allgemeinen (also bei anderen Daten aus der gleichen <a href="Grundgesamtheit" title="Grundgesamtheit">Grundgesamtheit</a>) nicht zu den wahren Vorhersagen beitragen<a href="#cite_note-2">[2]</a>.

Die zweite Möglichkeit, die im Folgenden beschrieben wird, ist es zunächst einen relativ großen Baum <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/55b9e7d7b96196b5a6a26f4349caa3ac82fd67e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{0}}" loading="lazy"> zu konstruieren, der dann im Nachhinein beschnitten wird. Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\subset T_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\subset T_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53fe5e5032c6af110c4e0d090c36fda33fe45c4d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.147ex; height:2.509ex;" alt="{\displaystyle T\subset T_{0}}" loading="lazy"> ein echter <a href="Teilgraph" title="Teilgraph">Teilgraph</a>, der durch Entfernung inneren Knoten erzeugt werden kann (d. h. die Partitionen der Kinder dieses Knotens werden zusammengelegt). Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |T|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |T|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/073a0b1ce9d4c91f30329289adbb91aae47f87ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.93ex; height:2.843ex;" alt="{\displaystyle |T|}" loading="lazy"> die Anzahl der Blätter eines solchen Teilgraphs, wobei jedem Blatt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> die Partition <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{l}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c9f2439c2bbf45ac826eebcd1bca00db560479be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.486ex; height:2.509ex;" alt="{\displaystyle R_{l}}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |R_{l}|}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |R_{l}|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8fbed57340962a969a093d744fbb26b9519a5506.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.78ex; height:2.843ex;" alt="{\displaystyle |R_{l}|}" loading="lazy"> Elementen zugeordnet ist. Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {c}}_{l}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {c}}_{l}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b6d503d56294fc326e54cb4c11fe8b094934ef23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.014ex; height:2.509ex;" alt="{\displaystyle {\hat {c}}_{l}}" loading="lazy"> wie oben und

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{l}(T,{\mathcal {D_{t}}})={\frac {1}{|R_{l}|}}\sum _{x^{(i)}\in R_{l}}(y_{i}-{\hat {c}}_{l})^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b51a04e31a53729fa75499c21b09538b8a5ddd77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:32.927ex; height:7.176ex;" alt="{\displaystyle Q_{l}(T,{\mathcal {D_{t}}})={\frac {1}{|R_{l}|}}\sum _{x^{(i)}\in R_{l}}(y_{i}-{\hat {c}}_{l})^{2}}" loading="lazy">.</dd></dl>

Die Idee ist es einen Baum zu finden, der die Funktion

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\alpha }(T,{\mathcal {D_{t}}})=\sum _{l=1}^{|T|}|R_{l}|Q_{l}(T,{\mathcal {D_{t}}})+\alpha |T|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/13c98a70ef8e433cb85eb1dfbd06b1d3fdcec71c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:37.58ex; height:7.676ex;" alt="{\displaystyle C_{\alpha }(T,{\mathcal {D_{t}}})=\sum _{l=1}^{|T|}|R_{l}|Q_{l}(T,{\mathcal {D_{t}}})+\alpha |T|}" loading="lazy"></dd></dl>

für gegebenes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> minimiert. Hierzu wird eine von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3277962e1959c3241fb1b70c7f0ac6dcefebd966.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}" loading="lazy"> verschiedene Datenmenge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D_{t}}}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D_{t}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3cfac976b44bd6d2591dfed770d5f80847c1936c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.618ex; height:2.509ex;" alt="{\displaystyle {\mathcal {D_{t}}}}" loading="lazy"> (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> test set) benutzt, um einer Überanpassung vorzubeugen (vgl. <a href="Kreuzvalidierungsverfahren" title="Kreuzvalidierungsverfahren">Kreuzvalidierungsverfahren</a>).

Der frei wählbare Parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> beschreibt die Gewichtung zwischen Güte der Voraussage des Entscheidungsbaums und seiner Komplexität. Für gegebenes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> wird eine absteigende Sequenz von Teilbäumen erzeugt, indem bei jedem Schritt der innere Knoten entfernt wird, der den geringsten pro-Knoten Anstieg von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum \nolimits _{l}|R_{l}|Q_{l}(T,{\mathcal {D_{t}}})}">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum \nolimits _{l}|R_{l}|Q_{l}(T,{\mathcal {D_{t}}})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/39ac0e621f18095fb23efbe643049d6d1e0a3269.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:17.903ex; height:3.843ex;" alt="{\displaystyle \sum \nolimits _{l}|R_{l}|Q_{l}(T,{\mathcal {D_{t}}})}" loading="lazy"> erzeugt, bis nur noch ein einziger Knoten übrig ist. Es gibt dann einen eindeutig bestimmbaren kleinsten Teilbaum, der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\alpha }(T,{\mathcal {D_{t}}})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\alpha }(T,{\mathcal {D_{t}}})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b66361ef38c37818ab211d8a2c300d12003154a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.043ex; height:2.843ex;" alt="{\displaystyle C_{\alpha }(T,{\mathcal {D_{t}}})}" loading="lazy"> minimiert.

<div class="mw-heading mw-heading3"><h3 id="Klassifizierung">Klassifizierung</h3></div>

Seien nun die Ausgabewerte kategorisch, d. h. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {Y}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {Y}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8935ef8cf454efa0b58363386c33f16a48ec36ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.659ex; height:2.509ex;" alt="{\displaystyle {\mathcal {Y}}}" loading="lazy"> ist eine endliche Menge und <a href="Ohne_Beschr%C3%A4nkung_der_Allgemeinheit" title="Ohne Beschränkung der Allgemeinheit">o. B. d. A.</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}\in \{1,2,\dots ,K\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}\in \{1,2,\dots ,K\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5187004f353aa426e3e1e448c5b3788a8e33a7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.707ex; height:2.843ex;" alt="{\displaystyle y_{i}\in \{1,2,\dots ,K\}}" loading="lazy">. Die einzigen Änderungen des Algorithmus im Vergleich zur Regression betreffen die Fehlerfunktionen für die Konstruktion des Baums und das Pruning.

Wir definieren

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {p}}_{lk}:={\frac {1}{|R_{l}|}}\sum _{x_{i}\in R_{l}}I(y_{i}=k)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53c263f1c848b67600333c0d76a7d1c21ce98781.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; margin-left: -0.089ex; width:25.864ex; height:6.843ex;" alt="{\displaystyle {\hat {p}}_{lk}:={\frac {1}{|R_{l}|}}\sum _{x_{i}\in R_{l}}I(y_{i}=k)}" loading="lazy">,</dd></dl>

wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |R_{l}|}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |R_{l}|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8fbed57340962a969a093d744fbb26b9519a5506.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.78ex; height:2.843ex;" alt="{\displaystyle |R_{l}|}" loading="lazy"> gleich der Anzahl der Elemente in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{l}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c9f2439c2bbf45ac826eebcd1bca00db560479be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.486ex; height:2.509ex;" alt="{\displaystyle R_{l}}" loading="lazy"> sei und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I(\cdot )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I(\cdot )}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bbfc685a51919256883dacd3ad86eec3dc7a258.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.628ex; height:2.843ex;" alt="{\displaystyle I(\cdot )}" loading="lazy"> die <a href="Indikatorfunktion" title="Indikatorfunktion">Indikatorfunktion</a>.

Damit lässt sich nun in jeder Region <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{l}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c9f2439c2bbf45ac826eebcd1bca00db560479be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.486ex; height:2.509ex;" alt="{\displaystyle R_{l}}" loading="lazy"> die Klassifizierung der Einträge nach Mehrheitsentscheid durchführen:

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

<mtext>argmax</mtext>

</mrow>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{T}(x^{(i)}\in R_{l})={\textrm {argmax}}_{k}\,{\hat {p}}_{lk}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da5459ac1b592c90946d29deb9aa1bc60f4b71e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.149ex; height:3.343ex;" alt="{\displaystyle f_{T}(x^{(i)}\in R_{l})={\textrm {argmax}}_{k}\,{\hat {p}}_{lk}}" loading="lazy">.</dd></dl>

Mögliche Fehlerfunktionen geben die sogenannte Unreinheit der Partitionen an und können definiert werden als:

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{|R_{l}|}}\sum _{x_{i}\in R_{l}}I(y_{i}\neq k)=1-{\hat {p}}_{lk}\quad }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/675a6ca01854c97b2bd9237fad8affe65346303c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:31.453ex; height:6.843ex;" alt="{\displaystyle {\frac {1}{|R_{l}|}}\sum _{x_{i}\in R_{l}}I(y_{i}\neq k)=1-{\hat {p}}_{lk}\quad }" loading="lazy"> (Missklassifizerungsfehler)</dd>

</mrow>

</mrow>

</munderover>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{k=1}^{K}{\hat {p}}_{lk}(1-{\hat {p}}_{lk})\quad }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/88045ae63586653f7bc890db2ae289bd669a3cb8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.754ex; height:7.343ex;" alt="{\displaystyle \sum _{k=1}^{K}{\hat {p}}_{lk}(1-{\hat {p}}_{lk})\quad }" loading="lazy"> (<a href="Simpson-Index" title="Simpson-Index">Gini-Simpson-Index</a>)</dd>

</mrow>

</mrow>

</munderover>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -\sum _{k=1}^{K}{\hat {p}}_{lk}\log {\hat {p}}_{lk}\quad }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0557e161eef97b0b1ad24a7ea35f888fe162cef8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.883ex; height:7.343ex;" alt="{\displaystyle -\sum _{k=1}^{K}{\hat {p}}_{lk}\log {\hat {p}}_{lk}\quad }" loading="lazy"> (<a href="Kreuzentropie" title="Kreuzentropie">Kreuzentropie</a>, <a href="Shannon-Index" title="Shannon-Index">Shannon-Index</a>)</dd></dl>

Jede dieser Funktionen kann bei der Konstruktion eines Entscheidungsbaumes anstelle der mittleren quadratischen Abweichung genutzt werden, sodass der wesentliche Teil des Algorithmus unverändert bleibt.

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Iterative_Dichotomiser_3" title="Iterative Dichotomiser 3">Iterative Dichotomiser 3</a> (ID3)</li>

<li><a href="CHAID" title="CHAID">CHAID</a></li>

<li><a href="Klassifikationsbaum-Methode" title="Klassifikationsbaum-Methode">Klassifikationsbaum-Methode</a></li>

<li>Implementierungen

<ul><li>In <a href="R_(Programmiersprache)" title="R (Programmiersprache)">R</a>: <a rel="nofollow" class="external text" href="https://www.rdocumentation.org/packages/rpart/versions/4.1-15">rpart</a></li>

<li>In <a href="Python_(Programmiersprache)" title="Python (Programmiersprache)">Python</a> mit <a href="Scikit-learn" title="Scikit-learn">Scikit-learn</a>: <a rel="nofollow" class="external text" href="https://scikit-learn.org/stable/modules/tree.html#tree-algorithms">sklearn.tree</a></li></ul></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>T. Hastie, R. Tibshirani, J. Friedman: <a rel="nofollow" class="external text" href="https://web.stanford.edu/~hastie/ElemStatLearn/printings/ESLII_print12.pdf">The Elements of Statistical Learning: Data Mining, Inference, and Prediction.</a> Second Edition. Springer-Verlag New York, 2009, ISBN 978-0-387-84857-0</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone: CART: Classification and Regression Trees. Wadsworth: Belmont, CA, 1984.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> T. Grubinger, A. Zeileis, K.-P. Pfeiffer: <a rel="nofollow" class="external text" href="https://www.jstatsoft.org/article/view/v061i01">evtree: Evolutionary Learning of Globally Optimal Classification and Regression Trees in R</a>. Journal of Statistical Software. 2014, Volume 61, Issue 1

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-05-17" href="https://de.wikipedia.org/wiki/?title=CART_(Algorithmus)&oldid=256091557">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>